Section: New Results

Information spreading in dynamic graphs

We showed how a technique used to analyse the flooding completion time in the case of a special class of random evolving graph model, that is, the edge-Markovian model, can be used in order to prove that the flooding completion time of a random evolving graph ${\left(G_t\right)}_{t\ge 0}$ is bounded by $kD+2C$, where intuitively (1) $k$ is the smallest time necessary for the rising of a giant component, (2) $D$ is the diameter of the giant component, and (3) $C$ is the time required for the nodes outside the giant component to eventually get an edge connecting them to the giant component [30] . Then, based on this result, we developed a general methodology for analysing flooding in sequences of random graphs and we applied this general methodology to the case of power-law evolving graphs (that is, sequences of mutually independent random graphs such that the number $y$ of nodes of degree $x$ distributes like $1/x^{\beta }$ for some $\beta >0$), and to the case of an arbitrary given degree distribution.